package com.review.dp;

import com.leetcode.LC_MED.TreeNode;

import java.util.HashMap;

public class LC_337 {
    public int rob(TreeNode root) {
        HashMap<TreeNode, Integer> memo = new HashMap<>();
        return dp(root, memo);
    }

    public int dp(TreeNode root, HashMap<TreeNode, Integer> memo) {
        if (root == null) {
            return 0;
        }
        if (memo.containsKey(root)) {
            return memo.get(root);
        }

        int money = root.val;

        if (root.left != null) {
            money += dp(root.left.left, memo) + dp(root.left.right, memo);
        }
        if (root.right != null) {
            money += dp(root.right.left, memo) + dp(root.right.right, memo);
        }
        int res = Math.max(Math.max(money, dp(root.left, memo)), dp(root.right, memo));
        memo.put(root, res);
        return res;
    }
}
